package topics;

import java.util.HashSet;
import java.util.Set;

/**
 * @program: common_parents
 * @description: 无重复字符的最长子串
 * @author: jatej
 * @create: 2021-06-08 09:42
 **/
public class LengthOfLongestSubstring {
    /**
     * 题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串的长度。
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 链接地址：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
     **/
    public static void main(String[] args) {
        String str1 = "abcabcbb";//输出3
        String str2 = "bbbbb";//输出1
        String str3 = "pwwkew";//输出3
        String str4 = " ";//输出1
        //方法一
        System.out.println(lengthOfLongestSubstring1(str1));
        System.out.println(lengthOfLongestSubstring1(str2));
        System.out.println(lengthOfLongestSubstring1(str3));
        System.out.println(lengthOfLongestSubstring1(str4));
        //方法二
        System.out.println(lengthOfLongestSubstring2(str1));
        System.out.println(lengthOfLongestSubstring2(str2));
        System.out.println(lengthOfLongestSubstring2(str3));
        System.out.println(lengthOfLongestSubstring2(str4));
    }

    /**
     * @Author jatej
     * @Description 思路一：采用左右坐标移动截取字符数组的方式
     * @Date 2021/6/8 9:45
     **/
    public static int lengthOfLongestSubstring1(String s) {
        //第一步：判断去空
        if (s == null || s.equals("")) {
            return 0;
        }
        char[] charArray = s.toCharArray();//将字符串转换为字符数组
        int maxLength = 0;//定义最大长度，用于比较
        int rk = -1;//定义数组的右坐标位置
        Set<Character> set = new HashSet<Character>();//定义set集合，用于存放不重复的字符
        for (int i = 0; i < charArray.length; i++) {//循环遍历字符数组，i可以当做左坐标
            if (i != 0) {
                set.remove(charArray[i - 1]);//左坐标移动一位，则删除前一个位置的字符
            }
            //当满足条件时，右坐标持续添加字符进set中
            //右坐标下一位不超过最大字符长度，右坐标下一位字符不在集合中
            while (rk + 1 < charArray.length && !set.contains(charArray[rk + 1])) {
                set.add(charArray[rk + 1]);
                rk++;
            }
            //长度比价
            maxLength = maxLength > set.size() ? maxLength : set.size();
        }
        return maxLength;
    }

    /**
     * @Author jatej
     * @Description 思路二：采用字符串截取的方法
     * @Date 2021/6/8 9:45
     **/
    public static int lengthOfLongestSubstring2(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }
        int maxLength = 0;//定义字符无重复最长长度
        int from = 0;//左边位置
        int to = 1;//右边位置
        while (to < s.length()) {//右坐标不大于字符串长度
            //截取from到to(不含to)的字符串，并判断截取后的字符串是否包含to位置的字符
            int site = s.substring(from, to).indexOf(s.charAt(to));
            if (site != -1) {//表示截取的字符串中包含有to位置的字符
                //比较已有区间长度与maxLength
                maxLength = maxLength > (to - from) ? maxLength : (to - from);
                if (maxLength > (s.length() - from + 1)) {//目前最大长度已经大于剩余字符的长度
                    break;
                }
                from = from + site + 1;//将起始位置移到重复字符的下一位
            }
            to++;
        }
        //再次进行长度比较
        maxLength = maxLength > (to - from) ? maxLength : (to - from);
        return maxLength;
    }

}
